package leetcode.primary;

import utils.linkedList.LinkedList;
import utils.linkedList.ListNode;

public class T234 {
    public boolean isPalindrome(ListNode head) {
        if (head.next==null){
            return true;
        }

        ListNode leftMid,rightMid;
        ListNode p = head,q = head;
        ListNode pre = head,post = head.next;

        while (q.next!=null && q.next.next!=null){
            q=q.next.next;
            p = post;
            post = p.next;
            p.next = pre;
            pre = p;
        }

        System.out.println("p="+p.val+",q="+q.val);
        if (q.next==null){
            leftMid = p.next;
        }else {
            leftMid = p;
        }
        rightMid = post;

        p = leftMid;
        q = rightMid;
        System.out.println("leftMid="+leftMid.val+",rightMid="+rightMid.val);
        while (p!=null && q != null){
            if (p.val!=q.val){
                return false;
            }
            p = p.next;
            q = q.next;
        }

        return true;
    }

    public void reverseList(ListNode node){

    }

    public static void main(String[] args) {
        T234 t234 = new T234();
        LinkedList linkedList = new LinkedList();
        ListNode head = linkedList.initLinkedList(new int[]{1,2,1});
        boolean palindrome = t234.isPalindrome(head);
        System.out.println(palindrome);
    }
}
